
void HeapSortS2(vector<int> &arr1, int start, int end)
{

	int base = arr1[start];
	for (int i = start * 2 + 1; i <= end; i=i*2+1) //这里取等号，是因为外围传进来的是数组下标
	{
		if (i < end && arr1[i] < arr1[i+1])  //这里是做什么：是为了找到两个子节点的最大值，方便后续和父节点交换
		{
			i++;
		}

		if (arr1[i] > base)
		{
			arr1[start] = arr1[i];
			start = i;
		}
		else
		{
			break; //为什么这里可以break：因为是倒着调用函数的，既然都满足大小顺序，那就不用再接着遍历了
		}
	}

	//交换
	arr1[start] = base;
	return;
}

//堆排序，大根堆，然后把值移到最后，再构建大根堆，一次循环直到结束
//注意所有的下标都是基于非叶子的子节点

void HeapSortS1(vector<int> &arr1, int length)
{

	//倒序
	for (int i = (length-1-1)/2;i>=0;i--)
	{

		HeapSortS2(arr1, i, length-1);
	}

	//移动到最后
	int tmp = 0;
	for (int i = 0;i<length-1;i++)
	{
		tmp = arr1[0];
		arr1[0] = arr1[length - 1 - i]; //第一个元素和最后一个元素交换
		arr1[length - 1 - i] = tmp;
		HeapSortS2(arr1, 0, length - 1-i-1);//这个时候实际的下标值在原有基础上要上一个，因为少的那一个已经排序完成了的

	}

}

void HeapSort4(vector<int> &arr1, int length)
{
	SimplePrint(arr1, length, "原始数据：");

	HeapSortS1(arr1, length);

	SimplePrint(arr1, length, "排序后的数据：");
	return;
}

int main()
{

	vector<int> arr = {32,4,-2,45,6,10,32,100,10};
	//简单排序，双循环遍历
	//SimpleSort(arr,arr.size());
	//BublingSort(arr, arr.size());
	HeapSort4(arr, arr.size());
	//QuickSort();
	return 0;
}




//以下部分为重复代码，加深理解用
void HeapAdjust1(vector<int> &arr1, int start,int end)
{
	int tmp = arr1[start];
	for (int i = 2 * start + 1; i <= end; i=i*2+1) //遍历子树
	{
		if (i < end && arr1[i] < arr1[i + 1])
		{
			i++;
		}
		//一定是左右孩子的最大值
		if (arr1[i] > tmp) //子节点比父节点大的时候，需要交换
		{
			arr1[start] = arr1[i];
			start = i;
		}
		else
		{
			break;
		}

	}
	arr1[start] = tmp;

	return;
}
void HeapSort1(vector<int> &arr1, int length)
{
	//原理：有大小堆得概念：
	//第一次建立大根堆，从后往前依次调整
	//为什么-1还要再-1呢，这是因为二叉树的特性决定，跟节点为2*n+1
	for (int i = (length - 1 - 1) / 2; i >= 0; i--)//为什么是这个顺序呢，这就是二叉树拉平后对应到数据的位置
	{
		HeapAdjust1(arr1,i,length-1);
	}
	SimplePrint(arr1, length, "第一次heapadjust的数据：");

	//每次将根与待排序的最后一次交换，然后再调整
	int tmp;
	for (int i = 0; i < length - 1; i++)
	{
		tmp = arr1[0];
		arr1[0] = arr1[length - 1 - i];
		arr1[length - 1 - i] = tmp;
		HeapAdjust1(arr1, 0, length - 1 - i - 1);
		SimplePrint(arr1, length, "第二次heapadjust的数据：");
	}
	
	return;


}
//以上部分为重复代码，加深理解用